package LC;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/
 * You are given a string, s, and a list of words,
 * words, that are all of the same length.
 * Find all starting indices of substring(s) in s that is a concatenation of each word in words
 * exactly once and without any intervening characters.
 * For example, given:
 * s: "barfoothefoobarman"
 * words: ["foo", "bar"]
 * You should return the indices: [0,9].
 * (order does not matter).
 * 给定一个目标字符串s，一个单词集合words。
 * 要求使得words集合中所有元素连续出现在s中的首位置组成的集合（元素顺序不考虑）。
 */
public class LC_030_SubstringwithConcatenationofAllWords_HashMap_SlidingWindow {
    public static void main(String[] args) {
        String s = "barfoobarthefoobarmanfoobarbarfoo";
        String[] words = {"foo", "bar"};
        List<Integer> res = Solution.findSubstring(s, words);
        System.out.println(res.toString());
    }

    static class Solution {
        static List<Integer> findSubstring(String s, String[] words) {
            ArrayList<Integer> result = new ArrayList<>();
            if (s == null || s.length() == 0 || words == null || words.length == 0) return result;
            HashMap<String, Integer> map = new HashMap<>();
            for (String w : words) {
                if (map.containsKey(w))
                    map.put(w, map.get(w) + 1);
                else
                    map.put(w, 1);
            }
            int len = words[0].length();
            for (int j = 0; j < len; j++) {
                HashMap<String, Integer> hm = new HashMap<>();
                int start = j;
                int count = 0;
                for (int i = j; i <= s.length() - len; i = i + len) {
                    String sub = s.substring(i, i + len);
                    if (map.containsKey(sub)) {
                        if (hm.containsKey(sub))
                            hm.put(sub, hm.get(sub) + 1);
                        else
                            hm.put(sub, 1);
                        count++;
                        while (hm.get(sub) > map.get(sub)) {
                            String left = s.substring(start, start + len);
                            hm.put(left, hm.get(left) - 1);
                            count--;
                            start = start + len;
                        }
                        if (count == words.length) {
                            result.add(start);
                            String left = s.substring(start, start + len);
                            hm.put(left, hm.get(left) - 1);
                            count--;
                            start = start + len;
                        }
                    } else {
                        hm.clear();
                        start = i + len;
                        count = 0;
                    }
                }
            }
            return result;
        }
    }
}
